import java.net.Inet4Address;
import java.util.*;
class Nodes {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> arr=new ArrayList<>();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    arr.add(tmp.val);
                    if(tmp.left!=null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.offer(tmp.right);
                    }
                }
                list.add(0,arr);
            }
        }
        return list;
    }













    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if(root==null){
            return null;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        if(left==right){
            return root;
        }
        if(left>right){
            return subtreeWithAllDeepest(root.left);
        }
        return subtreeWithAllDeepest(root.right);
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(dfs(root.left),dfs(root.right))+1;
    }











    public TreeNode lcaDeepestLeaves(TreeNode root) {
        if(root==null){
            return null;
        }
        int left=dfss(root.left);
        int right=dfss(root.right);
        if(left==right){
            return root;
        }
        if(left<right){
            return lcaDeepestLeaves(root.right);
        }
        return lcaDeepestLeaves(root.left);
    }
    public int dfss(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(dfss(root.left),dfss(root.right))+1;
    }











    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null){
            return root;
        }
        convertBST(root.right);
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);
        return root;
    }











    public List<TreeNode> generateTrees(int n) {
        if(n==0){
            return new ArrayList<>();
        }
        return generateTrees2(1,n);
    }
    public List<TreeNode> generateTrees2(int start,int end){
        List<TreeNode> list=new ArrayList<>();
        if(start>end){
            list.add(null);
            return list;
        }
        for(int i=start;i<=end;i++){
            List<TreeNode> left=generateTrees2(start,i-1);
            List<TreeNode> right=generateTrees2(i+1,end);
            for(TreeNode l : left){
                for(TreeNode r : right){
                    TreeNode cur=new TreeNode(i);
                    cur.left=l;
                    cur.right=r;
                    list.add(cur);
                }
            }
        }
        return list;
    }










    int sum=0;
    public TreeNode bstToGst(TreeNode root) {
        if(root==null){
            return root;
        }
        bstToGst(root.right);
        sum+=root.val;
        root.val=sum;
        bstToGst(root.left);
        return root;
    }







    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<Node> queue=new LinkedList<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> arr=new ArrayList<>();
                for(int i=0;i<size;i++){
                    Node tmp=queue.poll();
                    arr.add(tmp.val);
                    for(Node cur : tmp.children){
                        queue.offer(cur);
                    }
                }
                list.add(arr);
            }
        }
        return list;
    }












    //层序遍历
    public Node connect(Node root) {
        if(root==null){
            return null;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                Node tmp= queue.poll();
                if(i<size-1){
                    tmp.next=queue.peek();
                }
                if(tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if(tmp.right!=null){
                    queue.offer(tmp.right);
                }
            }
        }
        return root;
    }









    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> list=new ArrayList<>();
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<cpdomains.length;i++){
            String[] str1=cpdomains[i].split(" ");
            int len1=Integer.valueOf(str1[0]);
            String[] str2=str1[1].split("\\.");
            int len2=str2.length;
            String str3="";
            for(int j=len2-1;j>=0;j--){
                if(j==len2-1){
                    str3=str2[j];
                }else{
                    str3=str2[j]+"."+str3;
                }
                map.put(str3,map.getOrDefault(str3,0)+len1);
            }
        }
        for(String s : map.keySet()){
            String str="";
            str=map.get(s)+" "+s;
            list.add(str);
        }
        return list;
    }








    //滑动窗口法
    public int[][] findContinuousSequence(int target) {
        List<int[]> list=new ArrayList<>();//顺序表
        int left=1;//左指针
        int right=1;//右指针
        int sum=0;//窗口和
        while(left<=target/2){//输出所有和为 target 的连续正整数序列（至少含有两个数），不可能大于target/2+1。
            if(sum<target){//窗口和小于目标值
                sum+=right;//窗口和加右指针所指元素
                right++;//右指针，右移
            }else if(sum>target){//窗口和大于目标值
                sum-=left;//窗口和减左指针所指元素
                left++;//左指针，右移
            }else{//窗口和与目标值相等
                int[] arr=new int[right-left];//保存这一段窗口元素，数组大小等于right-left
                for(int i=left;i<right;i++){//左闭右开，包含左指针元素到右指针元素减一的位置
                    arr[i-left]=i;//计算下标，添加元素
                }
                list.add(arr);//加入顺序表
                sum-=left;//窗口和减左指针所指元素
                left++;//左指针，右移
            }
        }
        return list.toArray(new int[list.size()][]);//以二位数组的形式返回
    }














    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map=new HashMap<>();
        for(String s :words){
            if(map.get(s)!=null){
                map.put(s,map.get(s)+1);
            }else{
                map.put(s,1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> queue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(queue.size()<k){
                queue.offer(entry);
            }else{
                Map.Entry<String,Integer> top=queue.peek();
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(entry.getKey().compareTo(top.getKey())<0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }else{
                    if(entry.getValue().compareTo(top.getValue())>0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }




















    public List<String> topKFrequents(String[] words, int k) {
        HashMap<String,Integer> map=new HashMap<>();
        for(String s : words){
            if(map.get(s)!=null){
                map.put(s,map.get(s)+1);
            }else{
                map.put(s,1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> queue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(queue.size()<k){
                queue.offer(entry);
            }else{
                Map.Entry<String,Integer> top=queue.peek();
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(entry.getKey().compareTo(top.getKey())<0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }else{
                    if(entry.getValue().compareTo(top.getValue())>0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }
            }
        }
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
